/*
 * @lc app=leetcode.cn id=64 lang=javascript
 *
 * [64] 最小路径和
 */

// @lc code=start
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    let m=grid.length
    let n=grid[0].length
    let db=new Array(m).fill(0).map(()=>new Array(n).fill(0))
    
    db[0][0]=grid[0][0]
    for(let j=0;j<n;j++){
        db[0][j]=((db[0][j-1])||0)+grid[0][j]
    }
    for(let i=0;i<m;i++){
        db[i][0]=(db[i-1]?db[i-1][0]:0)+grid[i][0]
    }
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
          db[i][j]=Math.min(db[i-1][j],db[i][j-1])+grid[i][j]       
        }
    }
    return db[m-1][n-1]
};
// @lc code=end
minPathSum ([[1,3,1],[1,5,1],[4,2,1]])
